Some problems on induced subgraphs

DOI10.1016/J.DAM.2017.10.021MaRDI QIDQ1693168zbMATH OpenOpenAlexFDO

Authors Vaidy Sivaraman

Publication date 11 January 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.09349

zbMATH Keywords

chromatic numberinduced subgraphNP-completenessclique numberperfect graphforbidden induced subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Abstract: We discuss some problems related to induced subgraphs. The first problem is about getting a good upper bound for the chromatic number in terms of the clique number for graphs in which every induced cycle has length $3$ or $4$. The second problem is about the perfect chromatic number of a graph, which is the smallest number of perfect sets into which the vertex set of a graph can be partitioned. (A set of vertices is said to be perfect it it induces a perfect graph.) The third problem is on antichains in the induced subgraph ordering. The fourth problem is on graphs in which the difference between the chromatic number and the clique number is at most one for every induced subgraph of the graph. The fifth problem is on a weakening of the notorious ErdH{o}s-Hajnal conjecture. The last problem is on a conjecture of Gy'{a}rf'{a}s about $chi$-boundedness of a particular class of graphs.

Recommendations

• Induced cycles and chromatic number
• Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture
• A survey of \(\chi\)-boundedness
• scientific article; zbMATH DE number 4183452
• A note on perfect graphs

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Bisimplicial vertices in even-hole-free graphs
• Bounded clique cover of some sparse graphs
• Finding large holes
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• On rigid circuit graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On the divisibility of graphs
• Ramsey-type theorems
• Recognizing Berge graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Weakly triangulated graphs
• \(K_{4}\)-free graphs with no odd holes

Cited in

(8)

• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Graphs with girth 9 and without longer odd holes are 3-colourable
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• 2-divisibility of some odd hole free graphs
• scientific article; zbMATH DE number 5054185 (Why is no real title available?)
• Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture
• Divisibility and coloring of some \(P_5\)-free graphs
• A survey of \(\chi\)-boundedness

This page was built for publication: Some problems on induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1693168)