Search

International audience; An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: (i) v = u, (ii) e = f, or (iii) edge vu is from the set {e, f}. An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. The minimum number of colors needed for incidence coloring of a graph is called the incidence chromatic number.It was proved that at most Delta(G) + 5 colors are enough for an incidence coloring of any planar graph G except for Delta(G) = 6, in which case at most 12 colors are needed. It is also known that every planar graph G with girth at least 6 and Delta(G) >= 5 has incidence chromatic number at most Delta(G)+ 2.In this paper we present some results on graphs regarding their maximum degree and maximum average degree. We improve the bound for planar graphs with Delta(G) = 6. We show that the incidence chromatic number is at most Delta(G) + 2 for any graph G with mad(G) < 3 and Delta(G) = 4, and for any graph with mad(G) < 10/3 and Delta(G) >= 8.

The weight of an edge e is the degree-sum of its end-vertices. An edge e = u v is an ( i , j ) -edge if deg ( u ) ≤ i and deg ( v ) ≤ j . In 1955, Kotzig proved that every 3-connected planar graph contains an edge of weight at most 13. Later, Borodin extended this result to the class of simple planar graphs with minimum degree at least 3. If we consider the class of plane graphs with minimum degree two, the existence of an edge with small weight can be proved under various conditions (for example girth at least five or bounded number of adjacent vertices of degree two). In this paper we investigate the structure of edges in plane graphs with prescribed dual edge weight what is the minimum sum of degrees of two faces sharing an edge. We prove that every plane graph with minimum degree two and dual edge weight at least w ⁎ contains an edge of type ( 2 , 10 ) or ( 3 , 4 ) if w ⁎ = 9 , ( 2 , 10 ) or ( 3 , 3 ) if w ⁎ = 10 , ( 2 , 6 ) or ( 3 , 3 ) if w ⁎ ∈ { 11 , 12 , 13 } , ( 2 , 6 ) if w ⁎ = 14 , and ( 2 , 4 ) if w ⁎ ≥ 15 . Moreover, all the bounds are the best possible.

A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w for light K1,3 and C10.

Deciding whether a planar graph (even of maximum degree $4$) is $3$-colorable is NP-complete. Determining subclasses of planar graphs being $3$-colorable has a long history, but since Gr\"{o}tzsch's result that triangle-free planar graphs are such, most of the effort was focused to solving Havel's and Steinberg's conjectures. In this paper, we prove that every planar graph of maximum degree $4$ obtained as a subgraph of the medial graph of any bipartite plane graph is $3$-choosable. These graphs are allowed to have close triangles (even incident), and have no short cycles forbidden, hence representing an entirely different class than the graphs inferred by the above mentioned conjectures.

We study the families of plane graphs determined by lower bounds ?$\delta$?, ?$\rho$?, ?$w$?, ?$w^\ast$? on their vertex degrees, face sizes, edge weights and dual edge weights, respectively. Continuing the previous research of such families comprised of polyhedral graphs, we determine the quadruples ?$(2,\rho,w,w^\ast)$? for which the associated family is non-empty. In addition, we determine all quadruples which yield extremal families (in the sense that the increase of any value of a quadruple results in an empty family). Obravnavamo družine ravninskih grafov določenih s spodnjimi mejami ?$\delta$?, ?$\rho$?, ?$w$?, ?$w^\ast$? za njihove vozliščne stopnje, velikosti lic, uteži povezav in uteži dualnih povezav. Nadaljujujoč prejšnjo raziskavo takšnih družin sestavljenih iz poliedrskih grafov določimo četverice ?$(2,\rho,w,w^\ast)$? za katere pridružena družina ni prazna. Poleg tega določimo vse četverice, ki imajo ekstremne družine (v tem smislu da s povečanjem katerekoli vrednosti četverice dobimo prazno družino).

International audience; In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i,j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than to contains a path of one of the types (Equation presented) Moreover, no parameter of this description can be improved.