On local structure of 1-planar graphs of minimum degree 5 and girth 4

Dávid Hudák; Tomás Madaras

Displaying similar documents to “On local structure of 1-planar graphs of minimum degree 5 and girth 4”

On ${(4, 1)}^{*}$ -choosability of toroidal graphs without chordal 7-cycles and adjacent 4-cycles

Haihui Zhang (2013)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

A graph $G$ is called ${(k, d)}^{*}$ -choosable if for every list assignment $L$ satisfying $| L (v) | = k$ for all $v \in V (G)$ , there is an $L$ -coloring of $G$ such that each vertex of $G$ has at most $d$ neighbors colored with the same color as itself. In this paper, it is proved that every toroidal graph without chordal 7-cycles and adjacent 4-cycles is ${(4, 1)}^{*}$ -choosable.

Paths with restricted degrees of their vertices in planar graphs

Stanislav Jendroľ (1999)

Czechoslovak Mathematical Journal

Similarity:

In this paper it is proved that every $3$ -connected planar graph contains a path on $3$ vertices each of which is of degree at most $15$ and a path on $4$ vertices each of which has degree at most $23$ . Analogous results are stated for $3$ -connected planar graphs of minimum degree $4$ and $5$ . Moreover, for every pair of integers $n \geq 3$ , $k \geq 4$ there is a $2$ -connected planar graph such that every path on $n$ vertices in it has a vertex of degree $k$ .

Join of two graphs admits a nowhere-zero $3$ -flow

Saieed Akbari, Maryam Aliakbarpour, Naryam Ghanbari, Emisa Nategh, Hossein Shahmohamad (2014)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a graph, and $λ$ the smallest integer for which $G$ has a nowhere-zero $λ$ -flow, i.e., an integer $λ$ for which $G$ admits a nowhere-zero $λ$ -flow, but it does not admit a $(λ - 1)$ -flow. We denote the minimum flow number of $G$ by $Λ (G)$ . In this paper we show that if $G$ and $H$ are two arbitrary graphs and $G$ has no isolated vertex, then $Λ (G \lor H) \leq 3$ except two cases: (i) One of the graphs $G$ and $H$ is $K_{2}$ and the other is $1$ -regular. (ii) $H = K_{1}$ and $G$ is a graph with at least one isolated vertex or a component whose every...

On integral sum graphs with a saturated vertex

Zhibo Chen (2010)

Czechoslovak Mathematical Journal

Similarity:

As introduced by F. Harary in 1994, a graph $G$ is said to be an $i n t e g r a l$ $s u m$ $g r a p h$ if its vertices can be given a labeling $f$ with distinct integers so that for any two distinct vertices $u$ and $v$ of $G$ , $u v$ is an edge of $G$ if and only if $f (u) + f (v) = f (w)$ for some vertex $w$ in $G$ . We prove that every integral sum graph with a saturated vertex, except the complete graph $K_{3}$ , has edge-chromatic number equal to its maximum degree. (A vertex of a graph $G$ is said to be if it is adjacent to every...

Vertex-disjoint stars in graphs

Katsuhiro Ota (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star $K_{1, t}$ . The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.

Displaying similar documents to “On local structure of 1-planar graphs of minimum degree 5 and girth 4”

On ( 4 , 1 ) * -choosability of toroidal graphs without chordal 7-cycles and adjacent 4-cycles

Paths with restricted degrees of their vertices in planar graphs

Join of two graphs admits a nowhere-zero 3 -flow

On integral sum graphs with a saturated vertex

Vertex-disjoint stars in graphs

On ${(4, 1)}^{*}$ -choosability of toroidal graphs without chordal 7-cycles and adjacent 4-cycles

Join of two graphs admits a nowhere-zero $3$ -flow