Clique-transversal sets and weak 2-colorings in graphs of small maximum degree

Clique-transversal sets and weak 2-colorings in graphs of small maximum degree

Graphs and Algorithms

Bibliographic Details
Main Authors:	Gábor Bacsó, Zsolt Tuza
Format:	Article
Language:	English
Published:	Discrete Mathematics & Theoretical Computer Science 2009-01-01
Series:	Discrete Mathematics & Theoretical Computer Science
Subjects:	[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
Online Access:	https://dmtcs.episciences.org/453/pdf

Similar Items

Clique cycle transversals in graphs with few P₄'s
by: Raquel Bravo, et al.
Published: (2013-09-01)

Complexity results on graphs with few cliques
by: Bill Rosgen, et al.
Published: (2007-01-01)

Cycle transversals in bounded degree graphs
by: Marina Groshaus, et al.
Published: (2011-03-01)

Independent sets in graphs with an excluded clique minor
by: David R. Wood
Published: (2007-01-01)

Random graphs with bounded maximum degree: asymptotic structure and a logical limit law
by: Vera Koponen
Published: (2012-11-01)

8-star-choosability of a graph with maximum average degree less than 3
by: Min Chen, et al.
Published: (2011-12-01)

All totally symmetric colored graphs
by: Mariusz Grech, et al.
Published: (2013-03-01)

An expected polynomial time algorithm for coloring 2-colorable 3-graphs
by: Yury Person, et al.
Published: (2011-05-01)

Irregular edge coloring of 2-regular graphs
by: Sylwia Cichacz, et al.
Published: (2011-02-01)

Immersion containment and connectivity in color-critical graphs
by: Faisal N. Abu-Khzam, et al.
Published: (2012-10-01)

Strong parity vertex coloring of plane graphs
by: Tomas Kaiser, et al.
Published: (2014-01-01)

Strong parity vertex coloring of plane graphs
by: Tomas Kaiser, et al.
Published: (2014-03-01)

On paths, trails and closed trails in edge-colored graphs
by: Laurent Gourvès, et al.
Published: (2012-09-01)

Bounded-degree graphs have arbitrarily large queue-number
by: David R. Wood
Published: (2008-01-01)

A note on compact and compact circular edge-colorings of graphs
by: Dariusz Dereniowski, et al.
Published: (2008-01-01)

Some results on stable sets for k-colorable P₆-free graphs and generalizations
by: Raffaele Mosca
Published: (2012-08-01)

New Upper Bounds for the Heights of Some Light Subgraphs in 1-Planar Graphs with High Minimum Degree
by: Xin Zhang, et al.
Published: (2011-09-01)

List edge and list total colorings of planar graphs without non-induced 7-cycles
by: Aijun Dong, et al.
Published: (2013-03-01)

Nonrepetitive colorings of lexicographic product of graphs
by: Balázs Keszegh, et al.
Published: (2014-10-01)

Detection number of bipartite graphs and cubic graphs
by: Frederic Havet, et al.
Published: (2014-12-01)

Acyclic chromatic index of fully subdivided graphs and Halin graphs
by: Manu Basavaraju
Published: (2012-10-01)

On the tileability of polygons with colored dominoes
by: Chris Worman, et al.
Published: (2007-01-01)

The location of the first maximum in the first sojourn of a Dyck path
by: Helmut Prodinger
Published: (2008-01-01)

Probe split graphs
by: Van Bang Le, et al.
Published: (2007-01-01)

Generation of Cubic graphs
by: Gunnar Brinkmann, et al.
Published: (2011-07-01)

On the complexity of vertex-coloring edge-weightings
by: Andrzej Dudek, et al.
Published: (2011-11-01)

Random Cayley digraphs of diameter 2 and given degree
by: Manuel E. Lladser, et al.
Published: (2012-09-01)

On economical set representations of graphs
by: Jing Kong, et al.
Published: (2009-01-01)

On the metric dimension of Grassmann graphs
by: Robert F. Bailey, et al.
Published: (2012-01-01)

On hereditary Helly classes of graphs
by: Marina Groshaus, et al.
Published: (2008-01-01)

The determining number of Kneser graphs
by: José Cáceres, et al.
Published: (2013-01-01)

On the chromatic number of some flip graphs
by: Ruy Fabila-Monroy, et al.
Published: (2009-01-01)

On 4-valent Frobenius circulant graphs
by: Sanming Zhou
Published: (2012-10-01)

The Erdős-Sós conjecture for geometric graphs
by: Luis Barba, et al.
Published: (2013-02-01)

Progress on the traceability conjecture for oriented graphs
by: Marietjie Frick, et al.
Published: (2008-01-01)

On Compact Encoding of Pagenumber $k$ Graphs
by: Cyril Gavoille, et al.
Published: (2008-01-01)

Extremal K_(s,t)-free bipartite graphs
by: Camino Balbuena, et al.
Published: (2008-01-01)

Upper k-tuple domination in graphs
by: Gerard Jennhwa Chang, et al.
Published: (2012-12-01)

Graphs with many vertex-disjoint cycles
by: Dieter Rautenbach, et al.
Published: (2012-09-01)

The resolving number of a graph Delia
by: Delia Garijo, et al.
Published: (2013-12-01)