Packing independent cliques into planar graphs
Authors:
- University of LouisvilleULUniversity of Louisville
- Csaba BiróCBCsaba Biró
- Gabriel ColladoGCGabriel Collado
- San José Universidad de Costa RicaSRSan José Universidad de Costa Rica
- Oscar ZamoraOZOscar Zamora
Open Access
- 1 January 2025
- journal article
- Published by Georgia Southern University in Theory and Applications of Graphs
- Vol. 12 (2) , 3
Abstract
The indeque number of a graph is largest set of vertices that induce an independent set of cliques. We study the extremal value of this parameter for the class and subclasses of planar graphs, most notably for forests and graphs of pathwidth at most $2$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free GraphsTheory of Computing Systems, 2024
- On the d-Claw Vertex Deletion ProblemAlgorithmica, 2023
- Large induced forests in planar graphs with girth 4Discrete Applied Mathematics, 2019
- The maximum independent union of cliques problem: complexity and exact approachesJournal of Global Optimization, 2018
- Minimum size of feedback vertex sets of planar graphs of girth at least fiveEuropean Journal of Combinatorics, 2017
- Large Induced Forests in GraphsJournal of Graph Theory, 2016
- Posets with Cover Graph of Pathwidth two have Bounded DimensionOrder, 2015
- Node-Deletion Problems on Bipartite GraphsSIAM Journal on Computing, 1981
- The node-deletion problem for hereditary properties is NP-completeJournal of Computer and System Sciences, 1980
- On acyclic colorings of planar graphsDiscrete Mathematics, 1979