Currently displaying 1 – 20 of 23

Showing per page

Order by Relevance | Title | Year of publication

Choice-Perfect Graphs

Zsolt Tuza — 2013

Discussiones Mathematicae Graph Theory

Given a graph G = (V,E) and a set Lv of admissible colors for each vertex v ∈ V (termed the list at v), a list coloring of G is a (proper) vertex coloring ϕ : V → S v2V Lv such that ϕ(v) ∈ Lv for all v ∈ V and ϕ(u) 6= ϕ(v) for all uv ∈ E. If such a ϕ exists, G is said to be list colorable. The choice number of G is the smallest natural number k for which G is list colorable whenever each list contains at least k colors. In this note we initiate the study of graphs in which the choice number equals...

Graph colorings with local constraints - a survey

Zsolt Tuza — 1997

Discussiones Mathematicae Graph Theory

We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers c v for the vertices v ∈ V are given, and the question is whether...

Decompositions of Plane Graphs Under Parity Constrains Given by Faces

Július CzapZsolt Tuza — 2013

Discussiones Mathematicae Graph Theory

An edge coloring of a plane graph G is facially proper if no two faceadjacent edges of G receive the same color. A facial (facially proper) parity edge coloring of a plane graph G is an (facially proper) edge coloring with the property that, for each color c and each face f of G, either an odd number of edges incident with f is colored with c, or color c does not occur on the edges of f. In this paper we deal with the following question: For which integers k does there exist a facial (facially proper)...

Generalized colorings and avoidable orientations

Jenő SzigetiZsolt Tuza — 1997

Discussiones Mathematicae Graph Theory

Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed...

Graphs without induced P₅ and C₅

Gabor BacsóZsolt Tuza — 2004

Discussiones Mathematicae Graph Theory

Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.

The cost chromatic number and hypergraph parameters

Gábor BacsóZsolt Tuza — 2006

Discussiones Mathematicae Graph Theory

In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.

K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

Csilla BujtásZsolt Tuza — 2016

Discussiones Mathematicae Graph Theory

A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K3-WORM colorable graphs which have a K3-WORM coloring with...

Color-bounded hypergraphs, V: host graphs and subdivisions

Csilla BujtásZsolt TuzaVitaly Voloshin — 2011

Discussiones Mathematicae Graph Theory

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = E₁,...,Eₘ, together with integers s i and t i satisfying 1 s i t i | E i | for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge E i satisfies s i | φ ( E i ) | t i . The hypergraph ℋ is colorable if it admits at least one proper coloring. We consider hypergraphs ℋ over a “host graph”, that means a graph G on the same vertex set X as ℋ, such that each E i induces a connected subgraph in G. In the current...

Dominating bipartite subgraphs in graphs

Gábor BacsóDanuta MichalakZsolt Tuza — 2005

Discussiones Mathematicae Graph Theory

A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.

Domination in partitioned graphs

Zsolt TuzaPreben Dahl Vestergaard — 2002

Discussiones Mathematicae Graph Theory

Let V₁, V₂ be a partition of the vertex set in a graph G, and let γ i denote the least number of vertices needed in G to dominate V i . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value...

Graph domination in distance two

Gábor BacsóAttila TálosZsolt Tuza — 2005

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that D o m D o m u = D o m u holds for u = all connected graphs without induced P u (u ≥ 2). (In particular, ₂ = K₁ and...

Page 1 Next

Download Results (CSV)