Graphs with no induced \(C_ 4\) and \(2K_ 2\)
From MaRDI portal
Publication:1801686
DOI10.1016/0012-365X(93)90477-BzbMath0772.05082OpenAlexW179301118MaRDI QIDQ1801686
Zsolt Tuza, András Pluhár, Mihály Hujter, Zoltán L. Blázsik
Publication date: 20 June 1993
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(93)90477-b
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)
Related Items (40)
Linear recognition of pseudo-split graphs ⋮ On realization graphs of degree sequences ⋮ Chromatic bounds for the subclasses of \(pK_2\)-free graphs ⋮ Split graphs and Nordhaus-Gaddum graphs ⋮ On the chromatic number of \(2 K_2\)-free graphs ⋮ Vizing bound for the chromatic number on some graph classes ⋮ Star chromatic bounds ⋮ On graphs without \(P_ 5\) and \(\overline {P}_ 5\) ⋮ On the use of Boolean methods for the computation of the stability number ⋮ Star coloring of graphs with girth at least five ⋮ Vertex coloring of graphs with few obstructions ⋮ Graph classes with linear Ramsey numbers ⋮ Hereditary unigraphs and Erdős-Gallai equalities ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ On fractional realizations of graph degree sequences ⋮ Bounds for the chromatic number of some \(pK_2\)-free graphs ⋮ Some good characterization results relating to the Kőnig-Egerváry theorem ⋮ Coloring of a superclass of \(2K_2\)-free graphs ⋮ Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs ⋮ Indicated coloring of the Mycielskian of some families of graphs ⋮ Near optimal colourability on hereditary graph families ⋮ Split graphs and block representations ⋮ Reconfiguration of vertex colouring and forbidden induced subgraphs ⋮ Colouring of \((P_3 \cup P_2)\)-free graphs ⋮ Star coloring of certain graph classes ⋮ Powers of ideals associated to \((C_{4},2K_{2})\)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Non-minimal degree-sequence-forcing triples ⋮ Recognition of split-graphic sequences ⋮ Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs ⋮ Chromatic bounds for some classes of \(2 K_2\)-free graphs ⋮ On the complete width and edge clique cover problems ⋮ Dynamically maintaining split graphs ⋮ On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets ⋮ Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum ⋮ Stability in \(P_5\)- and banner-free graphs ⋮ The structure of graphs with forbidden induced $C_4$, $\overline{C}_4$, $C_5$, $S_3$, chair and co-chair ⋮ On the stable set problem in special \(P_{5}\)-free graphs ⋮ Coloring of \((P_5, 4\)-wheel)-free graphs ⋮ Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs
Cites Work
This page was built for publication: Graphs with no induced \(C_ 4\) and \(2K_ 2\)
