Graphs with no induced C4 and 2K2

Zoltán L. Blázsik, Mihály Hujter, András Pluhár, Źsolt Tuza

Type: Article

Publication Date: 1993-05-01

Citations: 64

DOI: https://doi.org/10.1016/0012-365x(93)90477-b

View Publication

Locations

Discrete Mathematics - View

Similar Works

Action	Title	Year	Authors
+	Large regular graphs with no induced 2K 2	1992	M. Paoli G. W. Peck W. T. Trotter Douglas B. West
+	K 4-free graphs without large induced triangle-free subgraphs	2013	Guy Wolfovitz
+	Coloring graphs with no odd-K4	1998	Wenan Zang
+	Graphs in which each C4 spans K4	1996	Paul Erdős András Gyárfás Tomasz Łuczak
+	On graphs with no induced subdivision of K4	2012	Benjamin Lévêque Frédéric Maffray Nicolas Trotignon
+	Euler cycles in the complete graph K2m+1	1997	Tomáš Dvořák Ivan M. Havel Petr Liebl
+	Coloring (4K1,C4,C6)-free graphs	2022	Irena Penev
+	2-Colorings of complete graphs with a small number of monochromatic K4 subgraphs	1993	František Franěk V. Rödl
+	Contractible edges in a k-connected graph (K1 + P4)-free graph	2000	Kiyoshi Ando
+	K1,3-free and W4-free graphs	1996	Ton Kloks
+	K1,3-free and W4-free graphs	1994	A.J.J. Kloks
+	The number of C2-free graphs	2016	Robert Morris David Saxton
+	Cycles in k-connected graphs whose deletion results in a (k-2)-connected graph	1987	Yoshimi Egawa
+	On minimal non [h,2,1] graphs	2013	Liliana Alcón Marisa Gutiérrez María Pía Mazzoleni
+	Graphs with nullity 2c(G)+p(G)−1	2022	Long Wang Xianwen Fang Xianya Geng
+	On subgraphs of C2-free graphs	2017	Dániel Grósz Abhishek Methuku Casey Tompkins
+	CYCLES AND FACTORS IN CEKL4IN GRAPHS	1992	Jiping Liu
+	The class of {3K 1 , C 4 }-free graphs.	2005	S.A. Choudum M. A. Shalu
+	On K 1,3-free strictly Deza graphs	2017	A. V. Mityanina
+	Coloring Clean and K 4-Free Circle Graphs	2012	Alexandr Kostochka Kevin G. Milans

Works That Cite This (53)

Action	Title	Year	Authors
+	Polynomial $$\chi $$ χ -Binding Functions and Forbidden Induced Subgraphs: A Survey	2019	Ingo Schiermeyer Bert Randerath
+	Linear recognition of pseudo-split graphs	1994	Frédéric Maffray Myriam Preissmann
+	On the chromatic number of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" id="d1e28" altimg="si11.gif"><mml:mn>2</mml:mn><mml:msub><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:math>-free graphs	2018	Christoph Brause Bert Randerath Ingo Schiermeyer Elkin Vumar
+	Linearly <i>χ</i>‐bounding (<i>P</i><sub>6</sub>, <i>C</i><sub>4</sub>)‐free graphs*	2019	Serge Gaspers Shenwei Huang
+ PDF Chat	Near optimal colourability on hereditary graph families	2024	Yiao Ju Shenwei Huang
+ PDF Chat	Lovász-Schrijver PSD-Operator on Some Graph Classes Defined by Clique Cutsets	2018	Annegret K. Wagler
+	Cop number of $2K_2$-free graphs	2019	Vaidy Sivaraman Stephen M. Testa
+	Maximal cliques in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si27.gif" display="inline" overflow="scroll"><mml:mrow><mml:mo>{</mml:mo><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>∪</mml:mo><mml:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>3</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>C</mml:mi></mml:mrow><mml:mrow><mml:mn>4</mml:mn></mml:mrow></mml:msub><mml:mo…	2010	S.A. Choudum T. Karthick
+	Chromatic bounds for the subclasses of $pK_2$-free graphs	2021	Athmakoori Prashant S. Francis Raj M. Gokulnath
+	Coloring of ($P_5$, $4$-wheel)-free graphs	2020	Arnab Char T. Karthick

Works Cited by This (5)

Action	Title	Year	Authors
+	Covering all cliques of a graph	1990	Źsolt Tuza
+	A bound on the chromatic number of graphs without certain induced subgraphs	1980	Stanley Wagon
+	Covering the cliques of a graph with vertices	1992	P. Erdős Т. Галлаи Źsolt Tuza
+	Excluding induced subgraphs: quadrilaterals	1991	Hans Jürgen Prömel Angelika Steger
+ PDF Chat	Problems from the world surrounding perfect graphs	1987	András Gyárfás